package com.kevinkk.tree;

/**
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 相较于在普通二叉树里搜索，BST的性质是所有节点是有序的
 * 如果要查找两个节点的公共祖先，那么这个祖先的值肯定是介于这两个节点之间的
 * 【第一次】找到一个这两个节点之间的值时，这个值就是我们要找的公共祖先
 * 不存在，在找到这两个值之间的值后，还需要继续查找的情况，因为此时继续向下查找，势必会超过 p 和 q之间的范围
 */

public class LowestCommonAncestorOfABinarySearchTree {
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            while(root != null){
                if(root.val < p.val && root.val < q.val){
                    root = root.right;
                }else if(root.val > p.val && root.val > q.val){
                    root = root.left;
                }else{
                    break;
                }
            }
            return root;
        }
    }
}
